package leetcode.primary;

public class T338 {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        int powerOf2 = 1;
        ans[0] = 0;
        for (int i = 1;i<=n;i++){
            if (i<powerOf2){
                ans[i] = ans[i-powerOf2>>1]+1;
            }
            if (i==powerOf2){
                ans[i] = 1;
                powerOf2 = powerOf2<<1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        T338 t338 = new T338();
        int[] bits = t338.countBits(15);
        for (int bit : bits) {
            System.out.print(bit+" ");
        }
    }
}
